package basic.study.leetcode;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @ClassName Easy101
 * @Description
 * @Company inspur
 * @Author Kevin
 * @Date 2020/6/25 17:57
 * @Version 1.0
 */
public class Easy101 {

    class Solution {
        public boolean isSymmetric(TreeNode root) {
            return helper(root, root);
        }

        private boolean helper(TreeNode left, TreeNode right) {
            if (left == null && right == null) return true;
            if (left == null || right == null) return false;

            if (left.val != right.val) {
                return false;
            }

            return helper(left.left, right.right) && helper(left.right, right.left);
        }
    }

    class Solution1 {
        public boolean isSymmetric(TreeNode root) {
            if (root == null) return true;
            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(root);
            queue.offer(root);
            while (!queue.isEmpty()) {
                TreeNode left = queue.poll();
                TreeNode right = queue.poll();
                if (left == null && right == null) {
                    continue;
                }
                if (left == null || right == null) {
                    return false;
                }
                if (left.val != right.val) {
                    return false;
                }
                queue.offer(left.left);
                queue.offer(right.right);

                queue.offer(left.right);
                queue.offer(right.left);
            }
            return true;
        }
    }



    class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }
}
